package algorithms;

import org.springframework.web.bind.annotation.RequestMapping;

/**
 * @功能
 * @创建时间 2020/5/17
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {8, 1, 2, 6, 3};
        sort(arr);
        print(arr);
    }

    private static void sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            findMax(arr, i);
        }
    }

    static void findMax(int[] arr, int i) {
        int tmp=arr[i];
        int low,high,m,j;
        low=0;high=i-1;
        while (low<=high){
            m=(low+high)/2;
            if(arr[m]>tmp)
                high = m-1;
            else
                low = m+1;
        }
        for ( j =i-1;j>=high+1;j--)
            arr[j+1] = arr[j];
        arr[j+1] =tmp;
//        for (int j = i; j > 0; j--) {
//            if (arr[j-1] > arr[j ]) {
//                swap(arr, j-1, j );
//            }
//
//        }

    }

    public static void swap(int[] arr, int min, int max) {
        int tmp = arr[max];
        arr[max] = arr[min];
        arr[min] = tmp;
    }

    static void print(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i] + "");
        }
    }
}
